Exploring Real Mobility Data with M%2DAtlas.

Advanced knowledge discovery on movement data with the GeoPKDD system.

Towards discovery of eras in social networks.

As Time Goes by Discovering Eras in Evolving Social Networks.

DCUBE discrimination discovery in databases.

Preserving privacy in semantic%2Drich trajectories of human mobility.

Preserving privacy in semantic%2Drich trajectories of human mobility.

Integrating induction and deduction for finding evidence of discrimination.
Automatic Decision Support Systems (DSS) are widely adopted for screening purposes in socially sensitive tasks, including access to credit, mortgage, insurance, labor market and other benefits. While less arbitrary decisions can potentially be guaranteed, automatic DSS can still be discriminating in the socially negative sense of resulting in unfair or unequal treatment of people. We present a reference model for finding (prima facie) evidence of discrimination in automatic DSS which is driven by a few key legal concepts. First, frequent classification rules are extracted from the set of decisions taken by the DSS over an input pool dataset. Key legal concepts are then used to drive the analysis of the set of classification rules, with the aim of discovering patterns of discrimination. We present an implementation, called LP2DD, of the overall reference model integrating induction, through data mining classification rule extraction, and deduction, through a computational logic implementation of the analytical tools.
Data mining for discrimination discovery.
In the context of civil rights law, discrimination refers to unfair or unequal treatment of people based on membership to a category or a minority, without regard to individual merit. Discrimination in credit, mortgage, insurance, labor market, and education has been investigated by researchers in economics and human sciences. With the advent of automatic decision support systems, such as credit scoring systems, the ease of data collection opens several challenges to data analysts for the fight against discrimination. In this paper, we introduce the problem of discovering discrimination through data mining in a dataset of historical decision records, taken by humans or by automatic systems. We formalize the processes of direct and indirect discrimination discovery by modelling protected-by-law groups and contexts where discrimination occurs in a classification rule based syntax. Basically, classification rules extracted from the dataset allow for unveiling contexts of unlawful discrimination, where the degree of burden over protected-bylaw groups is formalized by an extension of the lift measure of a classification rule. In direct discrimination, the extracted rules can be directly mined in search of discriminatory contexts. In indirect discrimination, the mining process needs some background knowledge as a further input, e.g., census data, that combined with the extracted rules might allow for unveiling contexts of discriminatory decisions. A strategy adopted for combining extracted classification rules with background knowledge is called an inference model. In this paper, we propose two inference models and provide automatic procedures for their implementation. An empirical assessment of our results is provided on the German credit dataset and on the PKDD Discovery Challenge 1999 financial dataset.
Movement Data Anonymity through Generalization.

Mining Mobility Behavior from Trajectory Data.

Geographic privacy%2Daware knowledge discovery and delivery.
In this report, we summarize the events of the First International
Trajectory pattern analysis for urban traffic.

Integrating induction and deduction for finding evidence of discrimination.
Automatic Decision Support Systems (DSS) are widely adopted for screening purposes in socially sensitive tasks, including access to credit, mortgage, insurance, labor market and other benefits. While less arbitrary decisions can potentially be guaranteed, automatic DSS can still be discriminating in the socially negative sense of resulting in unfair or unequal treatment of people. We present a reference model for finding (prima facie) evidence of discrimination in automatic DSS which is driven by a few key legal concepts. First, frequent classification rules are extracted from the set of decisions taken by the DSS over an input pool dataset. Key legal concepts are then used to drive the analysis of the set of classification rules, with the aim of discovering patterns of discrimination. We present an implementation, called LP2DD, of the overall reference model integrating induction, through data mining classification rule extraction, and deduction, through a computational logic implementation of the analytical tools.
High Quality True%2DPositive Prediction for Fiscal Fraud Detection.

Measuring Discrimination in Socially%2DSensitive Decision Records.
Discrimination in social sense (e.g., against minorities and disadvantaged groups) is the subject of many laws worldwide, and it has been extensively studied in the social and economic sciences. We tackle the problem of determining, given a dataset of historical decision records, a precise measure of the degree of discrimination suffered by a given group (e.g., an etnic minority) in a given context (e.g., a geographic area) with respect to the decision (e.g. credit denial). In our approach, this problem is rephrased in a classification rule based setting, and a collection of quantitative measures of discrimination is introduced, on the basis of existing norms and regulations. The measures are defined as functions of the contingency table of a classification rule, and their statistical significance is assessed, relying on a large body of statistical inference methods for proportions. Based on this basic method, we are then able to address the more general problems of: (1) unveiling all discriminatory decision patterns hidden in the historical data, combining discrimination analysis with association rule mining, (2) unveiling discrimination in classifiers that learn over training data biased by discriminatory decisions, and (3) in the case of rule-based classifiers, sanitizing discriminatory rules by correcting their confidence. Our approach is validated on the German credit dataset and on the CPAR classifier. 1
Anonymous Sequences from Trajectory Data.

A Visual Analytics Toolkit for Cluster%2DBased Classification of Mobility Data.

A Visual Analytics Toolkit for Cluster%2DBased Classification of Mobility Data.

SNIPER A Data Mining Methodology for Fiscal Fraud Detection.

Mobility%2C Data Mining and Privacy %2D Geographic Knowledge Discovery

Discrimination%2Daware data mining.
In the context of civil rights law, discrimination refers to unfair or unequal treatment of people based on membership to a category or a minority, without regard to individual merit. Rules extracted from databases by data mining techniques, such as classification or association rules, when used for decision tasks such as benefit or credit approval, can be discriminatory in the above sense. In this paper, the notion of discriminatory classification rules is introduced and studied. Providing a guarantee of non-discrimination is shown to be a non trivial task. A naïve approach, like taking away all discriminatory attributes, is shown to be not enough when other background knowledge is available. Our approach leads to a precise formulation of the redlining problem along with a formal result relating discriminatory rules with apparently safe ones by means of background knowledge. An empirical assessment of the results on the German credit dataset is also provided.
Pattern%2DPreserving k%2DAnonymization of Sequences and its Application to Mobil%2D ity Data Mining.



Mobility%2C Data Mining and Privacy A Vision of Convergence.

Privacy Protection Regulations and Technologies%2C Opportunities and Threats.

Spatiotemporal Data Mining.
With some significant exceptions, current applications for data mining are either in those areas for which there is little accepted discovery methodology or are being used within a knowledge discovery process that does not expect authoritative results but finds the discovered rules useful none-the-less. This is in contrast to its application in the fields applicable to spatial or spatio-temporal discovery which possess a
Visually driven analysis of movement data by progressive clustering.

Anonymity preserving pattern discovery.

Anonymity preserving pattern discovery.

Trajectory pattern mining.
The constant increase of moving object data imposes the need for modeling, processing, and mining trajectories, in order to find and understand the patterns behind these data. Existing works have mainly focused on the geometric properties of trajectories, while the semantics and the background geographic information has rarely been addressed. We claim that meaningful patterns can only be extracted from trajectories if the geographic space where trajectories are located is considered. In this paper we propose a reverse engineering framework for mining and modeling semantic trajectory patterns. Since trajectory patterns are data dependent, they may not be modeled in conceptual geographic database schemas before they are known. Therefore, we apply data mining to extract general trajectory patterns, and through a new kind of relationships, we model these patterns in the geographic database schema. A case study shows the power of the framework for modeling semantic trajectory patterns in the geographic space.
Privacy%2DAware Knowledge Discovery from Location Data.

Towards low%2Dperturbation anonymity preserving pattern discovery.

Mining sequences with temporal annotations.
In this paper we propose an extension of the sequence mining paradigm to (temporally-)annotated sequential patterns, where each transition in a sequential pattern is annotated with a typical transition time derived from the source data. Then, we present a basic solution for the novel mining problem based on the combination of sequential pattern mining and clustering, and assess this solution on two realistic datasets, illustrating how potentially useful patterns of the new form are extracted. 1.
Efficient Mining of Temporally Annotated Sequences.

Time%2Dfocused clustering of trajectories of moving objects.

Blocking Anonymity Threats Raised by Frequent Itemset Mining.
In this paper we study when the disclosure of data mining results represents, per se, a threat to the anonymity of the individuals recorded in the analyzed database. The novelty of our approach is that we focus on an objective definition of privacy compliance of patterns without any reference to a preconceived knowledge of what is sensitive and what is not, on the basis of the rather intuitive and realistic constraint that the anonymity of individuals should be guaranteed. In particular, the problem addressed here arises from the possibility of inferring from the output of frequent itemset mining (i.e., a set of itemsets with support larger than a threshold σ), the existence of patterns with very low support (smaller than an anonymity threshold k)[3]. In the following we develop a simple methodology to block such inference opportunities by introducing distortion on the dangerous patterns. 1.
k%2DAnonymous Patterns.
Abstract. It is generally believed that data mining results do not violate the anonymity of the individuals recorded in the source database. In fact, data mining models and patterns, in order to ensure a required statistical significance, represent a large number of individuals and thus conceal individual identities: this is the case of the minimum support threshold in association rule mining. In this paper we show that this belief is ill-founded. By shifting the concept of k-anonymity from data to patterns, we formally characterize the notion of a threat to anonymity in the context of pattern discovery, and provide a methodology to efficiently and effectively identify all possible such threats that might arise from the disclosure of a set of extracted patterns. 1
Anonymity and data mining.
“Although nature commences with reason and ends with experience it is necessary for us to do the opposite, that is to commence with experience and from this to proceed to investigate the reason.” This thesis investigates two new research problems that arise in modern data mining: reasoning on data mining results, and privacy implication of data mining results. Most of the data mining algorithms rely on inductive techniques, trying to infer information that is generalized from the input data. But very often this inductive step on raw data is not enough to answer the user questions, and there is the need to process data again using other inference methods. In order to answer high level user needs such as explanation of results, we describe an environment able to perform abductive (hypothetical) reasoning, since often the solutions of such queries can be seen as the set of hypothesis that satisfy some requirements. By using cost-based abduction, we show how classification algorithms can be boosted by performing abductive reasoning over the data mining results, improving the quality
Exante A Preprocessing Method for Frequent%2DPattern Mining.

Efficient breadth%2Dfirst mining of frequent pattern with monotone constraints.

Machine Learning ECML 2004

Knowledge Discovery in Databases PKDD 2004

A Relational Query Primitive for Constraint%2DBased Pattern Mining.

Discovery of ads web hosts through traffic data analysis.

IT4PS information technology for problem solving.

Characterisations of Termination in Logic Programming.
The procedural interpretation of logic programs and queries  is parametric to the selection rule, i.e. the rule that determines which  atom is selected in each resolution step. Termination of logic programs  and queries depends critically on the selection rule. In this survey, we  present a unified view and comparison of seven notions of universal termination  considered in the literature, and the corresponding classes of  programs. For each class, we focus on a su#cient, and in most cases even  necessary, declarative characterisation for determining that a program is  in that class. By unifying di#erent formalisms and making appropriate  assumptions, we are able to establish a formal hierarchy between the  di#erent classes and their respective declarative characterisations.
Frequent Pattern Queries for Flexible Knowledge Discovery.

Bounded Nondeterminism of Logic Programs.
We introduce the notion of bounded nondeterminism for logic programs and  queries. A program and a query have bounded nondeterminism if there are  finitely many refutations for them via any selection rule. We o#er a declarative  characterization of the class of programs and queries that have bounded nondeterminism  by defining bounded programs and queries. The characterization  is provided in terms of Herbrand interpretations and level mappings, in the  style of existing characterizations of universal termination.
ExAMiner Optimized Level%2Dwise Frequent Pattern Mining with Monotone Constraint.
The key point of this paper is that, in frequent pattern mining, the most appropriate way of exploiting monotone constraints in conjunction with frequency is to use them in order to reduce the problem input together with the search space. Following this intuition, we introduce ExAMiner, a level-wise algorithm which exploits the real synergy of antimonotone and monotone constraints: the total benefit is greater than the sum of the two individual benefits. ExAMiner generalizes the basic idea of the preprocessing algorithm ExAnte [4], embedding such ideas at all levels of an Apriori-like computation. The resulting algorithm is the generalization of the Apriori algorithm when a conjunction of monotone constraints is conjoined to the frequency antimonotone constraint. Experimental results confirm that this is, so far, the most efficient way of attacking the computational problem in analysis.
Adaptive Constraint Pushing in Frequent Pattern Mining.
Abstract. Pushing monotone constraints in frequent pattern mining can help pruning the search space, but at the same time it can also reduce the effectiveness of anti-monotone pruning. There is a clear tradeoff. Is it better to exploit more monotone pruning at the cost of less antimonotone pruning, or viceversa? The answer depends on characteristics of the dataset and the selectivity of constraints. In this paper, we deeply characterize this trade-off and its related computational problem. As a result of this characterization, we introduce an adaptive strategy, named ACP (Adaptive Constraint Pushing) which exploits any conjunction of monotone and anti-monotone constraints to prune the search space, and level by level adapts the pruning to the input dataset and constraints, in order to maximize efficiency. 1
ExAnte Anticipated Data Reduction in Constrained Pattern Mining.
Constraint pushing techniques have been proven to be e#ective  in reducing the search space in the frequent pattern mining task,  and thus in improving e#ciency. But while pushing anti-monotone constraints  in a level-wise computation of frequent itemsets has been recognized  to be always profitable, the case is di#erent for monotone constraints.

WebCat Automatic Categorization of Web Search Results.


On logic programs that always succeed.

Negation as Failure through Abduction Reasoning about Termination.

The Declarative Side of Magic.

Classes of terminating logic programs.
The Constraint Logic Programming (CLP) Scheme merges logic programming with constraint solving over predefined domains. In this paper, we study proof methods for universal left termination of constraint logic programs. We provide a sound and complete characterization of left termination for ideal CLP languages which generalizes acceptability of logic programs. The characterization is then refined to the notion of partial acceptability, which is well-suited for automatic modular inference. We describe a theoretical framework for automation of the approach, which is implemented. For non-ideal CLP languages and without any assumption on their incomplete constraint solvers, even the most basic sound termination criterion from logic programming does not lift. We focus on a specific system, namely CLP(R), by proposing some additional conditions that make (partial) acceptability sound
Data Mining for Intelligent Web Caching.
The paper presents a vertical application of data warehousing and data mining technology:  intelligent web caching. We introduce several ways to construct intelligent web  caching algorithms that employ predictive models of web requests; the general idea is to  extend the LRU policy of web and proxy servers by making it sensible to web access models  extracted from web log data using data mining techniques. Two approaches have been  studied in particular, one based on association rules and another based on decision trees.
Classes of Terminating Logic Programs
The Constraint Logic Programming (CLP) Scheme merges logic programming with constraint solving over predefined domains. In this paper, we study proof methods for universal left termination of constraint logic programs. We provide a sound and complete characterization of left termination for ideal CLP languages which generalizes acceptability of logic programs. The characterization is then refined to the notion of partial acceptability, which is well-suited for automatic modular inference. We describe a theoretical framework for automation of the approach, which is implemented. For non-ideal CLP languages and without any assumption on their incomplete constraint solvers, even the most basic sound termination criterion from logic programming does not lift. We focus on a specific system, namely CLP(R), by proposing some additional conditions that make (partial) acceptability sound
Web log data warehousing and mining for intelligent web caching.
We introduce intelligent web caching algorithms that employ predictive models of web requests; the general idea is to extend the LRU policy of web and proxy servers by making it sensible to web access models extracted from web log data using data mining techniques. Two approaches have been studied in particular, frequent patterns and decision trees. The experimental results of the new algorithms show substantial improvement over existing LRU-based caching techniques, in terms of hit rate. We designed and developed a prototypical system, which supports data warehousing of web log data, extraction of data mining models and simulation of the web caching algorithms.
Nondeterministic%2C Nonmonotonic Logic Databases.
We consider in this paper an extension of Datalog with mechanisms for temporal, nonmonotonic and nondeterministic reasoning, which we refer to as Datalog++. We show, by means of examples, its flexibility in expressing queries concerning aggregates and data cube. Also, we show how iterated fixpoint and stable model semantics can be combined to the purpose of clarifying the semantics of Datalog++ programs, and supporting their efficient execution. Finally, we provide a more concrete implementation strategy, on which basis the design of optimization techniques tailored for Datalog++ is addressed.
Semantics and Expressive Power of Nondeterministic Constructs in Deductive Databases.

On Verification in Logic Database Languages.

Logic%2DBased Knowledge Discovery in Databases.
this paper, are extensively studied in [2, 4, 5, 10]
Foundations of distributed interaction systems.

Experiences with a Logic%2Dbased knowledge discovery Support Environment.

Using Data Mining Techniques in Fiscal Fraud Detection.
. Planning adequate audit strategies is a key success factor in &#034;a  posteriori&#034; fraud detection, e.g., in the fiscal and insurance domains, where  audits are intended to detect tax evasion and fraudulent claims. A case study is  presented in this paper, which illustrates how techniques based on classification  can be used to support the task of planning audit strategies. The proposed  approach is sensible to some conflicting issues of audit planning, e.g., the tradeoff  between maximizing audit benefits vs. minimizing audit costs.  1 Introduction  Fraud detection is becoming a central application area for knowledge discovery in databases, as it poses challenging technical and methodological problems, many of which are still open [1, 2]. A major task in fraud detection is that of constructing models, or profiles, of fraudulent behavior, which may serve in decision support systems for:  . preventing frauds (a priori fraud detection), or  . planning audit strategies (a posteriori fraud de...
Experiences with a Logic%2DBased Knowledge Discovery Support Environment.

Using Data Mining Techniques in Fiscal Fraud Detection.
. Planning adequate audit strategies is a key success factor in &#034;a  posteriori&#034; fraud detection, e.g., in the fiscal and insurance domains, where  audits are intended to detect tax evasion and fraudulent claims. A case study is  presented in this paper, which illustrates how techniques based on classification  can be used to support the task of planning audit strategies. The proposed  approach is sensible to some conflicting issues of audit planning, e.g., the tradeoff  between maximizing audit benefits vs. minimizing audit costs.  1 Introduction  Fraud detection is becoming a central application area for knowledge discovery in databases, as it poses challenging technical and methodological problems, many of which are still open [1, 2]. A major task in fraud detection is that of constructing models, or profiles, of fraudulent behavior, which may serve in decision support systems for:  . preventing frauds (a priori fraud detection), or  . planning audit strategies (a posteriori fraud de...
A Classification%2DBased Methodology for Planning Audit Strategies in Fraud Detection.
Planning adequate audit strategies is a key success factor in a posterion ’ fraud detection, e.g., in the fiscal and insurance domains, where audits are intended to detect tax evasion and fraudulent claims. A case study is presented in this paper, which illustrates how techniques based on classification can be used to support the task of planning audit strategies. The proposed approach is sensible to some conflicting issues of audit planning, e.g., the trade-off between maximizing audit benefits vs. minimizing audit costs. A methodological scenario, common to a whole class of similar applications, is then abstracted away from the case study. The limitations of available systems to support the identified overall KDD process, bring us to point out the key aspects of a logic-based database language, integrated with mining mechanisms, which is used to provide a uniform, highly expressive environment for the various steps in the construction of the considered case-study. Keywords Knowledge discovery in databases, data mining, classification, decision trees, fraud detection, logic-based database languages, integration of querying and mining. 1.
Integration of Deduction and Induction for Mining Supermarket Sales Data.

Una Metodologia Basata sulla Classificazione per la Pianificazione degli Accertamenti nel Rilevamento di Frodi.

On Logic Programs That Do Not Fail.
This paper investigates the advantages of reasoning on logic programs and queries that have only successful derivations. We consider an extension of the logic programming paradigm that combines guarded clauses, in the style of concurrent logic languages, and dynamic selection rules. Some general conditions for a class of programs and queries are stated, which characterize when successful derivations only are present. A few practical instances of the general conditions are studied, and their applicability to real programs demonstrated. The main contributions of the proposed method are: (i) don&#039;t care non determinism can be safely adopted for programs that do not fail, (ii) termination of process networks expressed as logic programs can be proved, by means of a simple proof method developed for a fixed selection rule, and (iii) a strategy for parallelizing terminating Prolog programs is identified.
Verification of Logic Programs.

On the Effective Semantics of Nondeterministic
We consider in this paper an extension of Datalog with mechanisms for temporal, nonmonotonic and nondeterministic reasoning, which we refer to as Datalog++. We study its semantics, and show how iterated fixpoint and stable model semantics can be combined to the purpose of clarifying the interpretation of Datalog++ programs, and supporting their efficient execution. On this basis, the design of appropriate optimization techniques for Datalog++ is also discussed.
Query Answering in Nondeterministic%2C Nonmonotonic Logic Databases.

Weakest Preconditions for Pure Prolog Programs.
We introduce a characterization of weakest preconditions and weakest liberal preconditions of pure Prolog programs P and postconditions Post in terms of ordinal closures of a natural operator based on P and Post .
Datalog with Non%2DDeterministic Choice Computers NDB%2DPTIME.

A Deductive Data Model for Representing and Querying Semistructured Data.
We show how the mechanisms of an active/deductive object-oriented model are capable of modeling the information available on the World Wide Web, the paradigmatic example of a large, distributed collection of poorly structured, heterogeneous information, consisting of documents connected by hypertext links. We exhibit the basic features of the object model, including the schema definition language, the query language with multiple roles, the basic update operations, and a form of active rules, and a compilation of the mentioned features into a fragment of  LDL++, which is essentially Datalog extended with non-determinism and a form of stratified negation. The proposed compilation has a twofold aim. On one side, it should provide an abstract implementation level, where the object model is declaratively reconstructed and its semantics clarified. On the other side, the proposed compilation should form the basis of a realistic implementation, as LDL++ can be efficiently executed, and suppor...
A Deductive Data Model for Representing and Querying Semistructured Data.
We show how the mechanisms of an active/deductive object-oriented model are capable of modeling the information available on the World Wide Web, the paradigmatic example of a large, distributed collection of poorly structured, heterogeneous information, consisting of documents connected by hypertext links. We exhibit the basic features of the object model, including the schema definition language, the query language with multiple roles, the basic update operations, and a form of active rules, and a compilation of the mentioned features into a fragment of  LDL++, which is essentially Datalog extended with non-determinism and a form of stratified negation. The proposed compilation has a twofold aim. On one side, it should provide an abstract implementation level, where the object model is declaratively reconstructed and its semantics clarified. On the other side, the proposed compilation should form the basis of a realistic implementation, as LDL++ can be efficiently executed, and suppor...
Datalog   A Basis for Active Object%2DOriented Databases.
We consider in this paper an extension of Datalog with mechanisms for temporal, non monotonic and non deterministic reasoning, which we refer to as Datalog++. First, we study its semantics, and show how iterated fixpoint and stable model semantics can be combined to the purpose of clarifying the interpretation of Datalog++ programs, and supporting their efficient execution. Second, we exhibit a compilation into Datalog++ of an active/deductive object-oriented model, ADOOD, including the schema definition language, the query language with multiple roles, the basic update operations, and a form of active rules. The proposed compilation is intended both to illustrate the expressiveness of Datalog++, and to provide a more flexible programming front-end to it. Finally, we illustrate the use of ADOOD by means of examples from semistructured data management.
Datalog   a Basis for Active Object.Oriented Databases.
We consider in this paper an extension of Datalog with mechanisms for temporal, non monotonic and non deterministic reasoning, which we refer to as Datalog++. First, we study its semantics, and show how iterated fixpoint and stable model semantics can be combined to the purpose of clarifying the interpretation of Datalog++ programs, and supporting their efficient execution. Second, we exhibit a compilation into Datalog++ of an active/deductive object-oriented model, ADOOD, including the schema definition language, the query language with multiple roles, the basic update operations, and a form of active rules. The proposed compilation is intended both to illustrate the expressiveness of Datalog++, and to provide a more flexible programming front-end to it. Finally, we illustrate the use of ADOOD by means of examples from semistructured data management.
Non%2Ddeterminism in Deductive Databases %2D Preface.

Verification of Meta%2DInterpreters.
A novel approach to the verification of meta-interpreters is introduced. We apply a general purpose verification method for logic programs, proposed in [28], to the case study of the Vanilla and other logic meta-interpreters. We extend the standard notion of declarative correctness, and design a criterion for proving correctness of meta-interpreters in a general sense, including amalgamated and reflective meta-interpreters.  The contribution of this paper can be summarized as follows: under certain natural assumptions, all interesting verification properties lift up from the object program to the meta-program, including partial correctness, termination, absence of errors, call patterns persistence, correct instances of queries, computed instances of queries. Interestingly, it is possible to establish these results on the basis of purely declarative reasoning, using the mentioned proof method.  We believe that the obtained results illustrate the broad applicability of the adopted verifi...
Logic in Databases
Logic and databases have gone a long way together since the  advent of relational databases. Already the first basic query languages for  relational databases beside relational algebra - tuple calculus and domain  calculus - are actually a subset of first order predicate logic. Furthermore  logic proved to be very adequate for establishing a sound theory for relational  databases.  When attempts were made to integrate AI and database technology in  form of expert database systems or knowledge base management systems  logic provided a unifying framework although several differences in the use  of logic in the both fields have been discovered. The confluence of logic  programming and databases triggered deductive databases as new area of  research.  In this overview paper we will discuss shortly the relationship between  relational databases and logic and present the possibilities for coupling  Prolog with databases. The main part of this paper concentrates on deductive  databases, in particular on the database language Datalog. We  conclude by mentioning some facets of recent research on logic and databases.  The goal of this paper is to provide an overview of the most relevant  developments in the field and providing pointers to the literature.  1 
A Closer Look at Declarative Interpretations.
Three semantics have been proposed as the most promising candidates for a declarative interpretation for logic programs and pure Prolog programs: the least Herbrand model, the least term model, i.e. the C-semantics, and the S-semantics. Previous results show that a strictly increasing information ordering between these semantics exists for the class of all programs. In particular, the S-semantics allows us to model the computed answer substitutions, which is not the case for the other two. We study here the relationship between these three semantics for specific classes of programs. We show that for a large class of programs (which is Turing complete) these three semantics are isomorphic. As a consequence, given a query, we can extract from the least Herbrand model of a program in this class all computed answer substitutions. However, for specific programs the least Herbrand model is tedious to construct and reason about because it contains &#034;ill-typed&#034; facts. Therefore we propose a fou...
Declarative Reconstruction of Updates in Logic Databases a Compilative Approach.

A Case Study in Logic Program Verification the Vanilla Metainterpreter.
We take the formal verification of the Vanilla metainterpreter as an excuse for explaining  a proof method for reasoning about logic programs. The choice of a semantics suitable for  program verification is discussed. We consider a variant of the least Herbrand model semantics  which abstracts from ill-typed atoms and the underlying (first order) language, thus enhancing  modularity and ease of specification. Then, proof outlines and proof obligations are introduced  in a Hoare&#039;s logic style. In the resulting proof theory, triples of the form fPregPfPostg can  be derived for a program P , which allow us to establish partial and total correctness. As a  consequence of our results, the correctness of Vanilla is directly proved (once again.)  Keywords: Verification, program development, metaprogramming, formal methods.  1 Introduction  Logic programming (and Prolog) is advertised as a declarative language, in the sense that specifications, when written in an appropriate syntax, can be dir...
Declarative Reconstruction of Updates in Logic Databases A Compilative Approach.

Termination is Language%2DIndependent.
We provide a generalized notion of recurrent and acceptable logic programs,  which abstracts from the rst order language underlying the program. On this  basis, we obtain a proof method for universal termination which is well suited  for modular reasoning, and directly reects programming practice. Applications  of the proposed approach include several natural proof obligations for modular  termination proofs, decidability results for the least term model semantics and  S-semantics.  Keywords. Termination, recurrent and acceptable programs, rst order theories,  least term model semantics, S-semantics.  1 Introduction  1.1 Motivations  A logic program is, by all means, a rst order theory. It is therefore legitimate to ask ourselves: which is the rst order language underlying a logic program? This issue is important for several reasons.   Most of (declarative) semantics are aected by the choice of the language. For instance, the least Herbrand model and the least term model semanti...
Proving termination of Prolog programs.
Acceptable logic programs have been studied extensively in the context of proving termination  of Prolog programs. It is difficult, however, to establish acceptability from the definition  since this depends on finding a suitable model, which need not be a Herbrand model in general,  together with a suitable level mapping that one can use to check the conditions which characterize  acceptability. In this paper, we will see that when working over a fixed but arbitrary  preinterpretation, a method can be provided for obtaining both a suitable model and a canonical  level mapping which are sufficient for this purpose. Furthermore, the canonical model and  level mapping obtained will turn out to be sufficient for discussing termination of non-ground  queries.  1 Introduction  Acceptable programs were first studied in detail in [AP93] where they were shown to coincide, if floundering is ignored, with the programs which are left-terminating. They have been much examined in the literature, fo...
A Proof Method for Runtime Properties of Prolog Programs.

Implementations of Program Composition Operations.
. This paper reports on a number of implementations for a  suite of composition operations of logic programs. We present and compare  three implementations, which rely on different techniques: metaprogramming,  program transformations, and extensions to the WAM,  respectively. In particular, we show how the third approach reduces the  drawbacks of the other two approaches, while retaining their advantages.  1 Introduction  The use of logic programming in different application domains has called for various extensions of the basic paradigm grounded on Horn clauses, in order to increase the expressive power of the formalism and to broaden its applicability. Indeed, the main aim of projects such as the Esprit Basic Research Action Compulog [9] is to identify the extension(s) of the basic paradigm of logic programming, which could form a computational logic for addressing the various aspects of computing.  Some of these extensions are aimed at providing enhanced knowledge representation an...
Expressive Power of Non%2DDeterministic Operators for Logic%2Dbased Languages.
Non-deterministic operators are needed in First-Order relational languages and Datalog to extend the expressive power of such languages and support efficient formulations of low complexity problems. In this paper, we study the operators proposed in the literature, including witness, lazy choice and dynamic choice, and compare their power of expressing deterministic and non-deterministic queries. We obtain a simple hierarchy that relates these operators with each other and with other constructs, such as negation and fixpoint.
Modular Logic Programming.
 
Datalog with Non%2DDeterministic Choice Computes NDB%2DPTIME.

Reasoning about Termination of Pure Prolog Programs
We provide a theoretical basis for studying termination of (general) logic programs with the Prolog selection rule. To this end we study the class of left terminating programs. These are logic programs that terminate with the Prolog selection rule for all ground goals. We offer a characterization of left terminating positive programs by means of the notion of an  acceptable program that provides us with a practical method of proving termination. The method is illustrated by giving a simple proof of termination of the quicksort program for the desired class of goals. Then we extend this approach to the class of general logic programs by modifying the concept of acceptability. We prove that acceptable general programs are left terminating. The converse implication does not hold but we show that under the assumption of nonfloundering from ground goals every left terminating general program is acceptable. Finally, we prove that various ways of defining semantics coincide for acceptable gen...
Meta for Modularising Logic Programming.

The Type System of LML.

Non%2DDeterminism in Deductive Databases.
This paper examines the problem of adding non-deterministic constructs to a declarative database language based on Horn Clause Logic. We revise a previously proposed approach, the choice construct introduced by Krishnamurthy and Naqvi, from the viewpoints of amenability to efficient implementation and expressive power.
Theory Construction in Computational Logic.

Proving Termination of General Prolog Programs.

Universal Quantification by Case Analysis.

Declarative Semantics for Pruning Operators in Logic Programming.
Stable models, a concept from autoepistemic logic, have been recently proposed  to define the semantics of logic programs with negation. A program  may have several stable models, and this multiplicity can be exploited to  characterize &#034;on&#039;t care&#034; nondeterminism, such as that arising from pruning  operators. In the (bottom-up) context of deductive databases, a semantics for  the nondeterministic choice construct was given by Sacca and Zaniolo. In  this paper, we extend their approach to handle the cut-tike pruning operators  in the top-down evaluation context, including the one-of and commit operators.
Algebraic Properties of a Class of Logic Programs.

Logic Programming within a Functional Framework.

A Transformational Approach to Negation in Logic Programming.

A Progress Report on the LML Project.

An Algebra of Logic Programs.
At present, the field of declarative programming is split into two main areas based on different formalisms; namely, functional programming, which is based on lambda calculus, and logic programming, which is based on firstorder logic. There are currently several language proposals for integrating the expressiveness of these two models of computation. In this thesis we work towards an integration of the methodology from the two research areas. To this end, we propose an algebraic approach to reasoning about logic programs, corresponding to the approach taken in functional programming. In the first half of the thesis we develop and discuss a framework which forms the basis for our algebraic analysis and transformation methods. The framework is based on an embedding of definite logic programs into lazy functional programs in Haskell, such that both the declarative and the operational semantics of the logic programs are preserved. In spite of its conciseness and apparent simplicity, the embedding proves to have many interesting properties and it gives rise to an algebraic semantics of logic programming. It also allows us to reason about logic programs in a simple calculational style, using rewriting and the algebraic laws of combinators. In the embedding, the meaning of a logic program arises compositionally from the meaning of its constituent subprograms and the combinators that connect them. In the second half of the thesis we explore applications of the embedding to the algebraic transformation of logic programs. A series of examples covers simple program derivations, where our techniques simplify some of the current techniques. Another set of examples explores applications of the more advanced program development techniques from the Algebra of Programming by Bird and de Moor [18], where we expand the techniques currently available for logic program derivation and optimisation. To my parents, Sandor and Erzsebet. And the end of all our exploring Will be to arrive where we started And know the place for the first time.
Complete Logic Programs with Domain%2DClosure Axiom.


Intensional Negation of Logic Programs Examples and Implementation Techniques.


The Type System of Galileo.

The Type System of Galileo.

Symbolic Semantics and Program Reduction.

